package sort

import "fmt"

func BubbleSortTest() {
	var array []int = []int{6, 5, 1, 2, 3}
	// BubbleSort(array)
	// OptimizeBubbleSort(array)
	// SelectionSort(array)
	// InsertSort(array)
	// QuickSort(array, 0, len(array)-1)
	// HeapSort(array)
	MergeSort(array, 0, len(array)-1)
	fmt.Println(array)
}

func BubbleSort(array []int) {
	for i := len(array) - 1; i > 0; i-- {
		for j := 0; j < i; j++ {
			if array[j] < array[j+1] {
				tmp := array[j]
				array[j] = array[j+1]
				array[j+1] = tmp
			}
		}
	}
}

func OptimizeBubbleSort(array []int) {
	lastSwapIndex := len(array) - 1
	sorted := true
	for lastSwapIndex > 0 {
		for i, size := 0, lastSwapIndex; i < size; i++ {
			if array[i] < array[i+1] {
				tmp := array[i]
				array[i] = array[i+1]
				array[i+1] = tmp
				sorted = false
			}
		}
		if sorted {
			break
		}
		lastSwapIndex--
	}
}

func SelectionSort(array []int) {
	len := len(array)
	for i := len - 1; i > 0; i-- {
		minIndex := i
		for j := 0; j < i; j++ {
			if array[minIndex] > array[j] {
				minIndex = j
			}
		}
		tmp := array[i]
		array[i] = array[minIndex]
		array[minIndex] = tmp
	}
}

func InsertSort(array []int) {
	for i := 1; i < len(array); i++ {
		tmp := array[i]
		j := i
		for ; j > 0 && array[j-1] > tmp; j-- {
			array[j] = array[j-1]
		}
		array[j] = tmp
	}
}

func QuickSort(array []int, left, right int) {
	if left >= right {
		return
	}
	i, j := left, right
	p := array[left]
	for i < j {
		for i < j && array[j] >= p {
			j--
		}
		for i < j && array[i] <= p {
			i++
		}
		if i < j {
			tmp := array[j]
			array[j] = array[i]
			array[i] = tmp
		}
	}
	array[left] = array[i]
	array[i] = p
	QuickSort(array, left, i-1)
	QuickSort(array, i+1, right)
}

func HeapSort(array []int) {
	len := len(array)
	for i := len / 2; i >= 0; i-- {
		HeapSink(array, i, len-1)
	}
	for i := len - 1; i >= 0; i-- {
		tmp := array[0]
		array[0] = array[i]
		array[i] = tmp
		HeapSink(array, 0, i-1)
	}
}
func HeapSink(array []int, index, lastIndex int) {
	p := index
	left, right := 2*index+1, 2*index+2
	if left <= lastIndex && array[left] < array[p] {
		p = left
	}
	if right <= lastIndex && array[right] < array[p] {
		p = right
	}
	if p != index {
		tmp := array[p]
		array[p] = array[index]
		array[index] = tmp
		HeapSink(array, p, lastIndex)
	}
}

func MergeSort(array []int, left, right int) {
	if left >= right {
		return
	}
	mid := (left + right) / 2
	MergeSort(array, left, mid)
	MergeSort(array, mid+1, right)
	Merge(array, left, mid, right)
}
func Merge(array []int, left, mid, right int) {
	tmpArray := make([]int, len(array))
	i, j := left, mid+1
	tmpIndex := 0
	for i <= mid && j <= right {
		for i <= mid && array[i] <= array[j] {
			tmpArray[tmpIndex] = array[i]
			i++
			tmpIndex++
		}
		for j <= right && array[j] <= array[i] {
			tmpArray[tmpIndex] = array[j]
			j++
			tmpIndex++
		}
	}
	for i <= mid {
		tmpArray[tmpIndex] = array[i]
		i++
		tmpIndex++
	}
	for j <= right {
		tmpArray[tmpIndex] = array[j]
		j++
		tmpIndex++
	}
	tmpIndex = 0
	for i := left; i <= right; i++ {
		array[i] = tmpArray[tmpIndex]
		tmpIndex++
	}
}
